package binaryTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    //遍历字符串
    public int i;
    static class TreeNode{
        //以内部类的方式定义树节点
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }

    //创建树
    public TreeNode createTree(String str) {
        //以先序遍历字符串创建树

        TreeNode node = null;
        if(str.charAt(i)=='#') {
            i++;
        } else {
            node = new TreeNode(str.charAt(i));
            i++;
            node.left = createTree(str);
            node.right = createTree(str);
        }
        return node;
    }

    //中序遍历
    public void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

    //层序遍历
    public void SequenceTraversal(TreeNode root) {
        if(root==null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode cur = null;
        queue.offer(root);
        while(!queue.isEmpty()) {
            cur = queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null) {
                queue.offer(cur.left);
            }
            if(cur.right!=null) {
                queue.offer(cur.right);
            }
        }
    }

   //层序遍历 需要将每层的值保存在List二维数组中
/**
 * 1：先将返回的二维数组创建，判断根节点是否为null，若是，则直接返回ret
 * 2：创建队列用于层序遍历，将root入队
 * 3：while循环，判定条件为队列不为空（由于前面已经将根节点入队，故第一次必定能执行）
 * 4：创建一维数组tmp，用于存储该层的节点，
 *      每次将队列中的所有节点全部存储进tmp并出队，出队的同时将该节点的左孩子 右孩子入队（为null不入队）
 *      每次循环结束，代表该层节点已全部储存，将tmp尾插ret
 *      当某一次将队列中的所有元素删除后，队列无补充，则退出循环
 * 5：退出循环，返回ret即可*/
    public List<List<Integer>> levelOrder(TreeNode root) {
        //先将返回的二维数组创建好
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        //创建栈 并将根节点插入
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            ArrayList<Integer> tmp = new ArrayList<>();
            int size = queue.size();
            while(size!=0) {
                TreeNode cur = queue.poll();
                //tmp.add(cur.val); ==》由于原题值为Integer 与此环境中的char不匹配，故注释
                if(cur.left!=null) {
                    queue.offer(cur.left);
                }
                if(cur.right!=null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(tmp);
        }
        return ret;
    }

    // 判断一棵树是不是完全二叉树
    /**
     * 由于完全二叉树的节点是按照从上到下 从左到右排列的
     * 从根节点开始，将节点出队后再将其两个子节点入队（不论是否为null）
     * 直到遇见null，break
     * 退出循环，对队列进行遍历，若是出现非null值，表示不是完全二叉树！*/
    public boolean isCompleteTree(TreeNode root) {
        //完全二叉树说明所有节点都是从上到下，从左到右
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur==null) {
                break;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        while(!queue.isEmpty()) {
            if(queue.poll()!=null) {
                return false;
            }
        }
        return true;
    }


}
